/**
 * @作者 钟先崟
 * @时间 2023-03-08 12:19
 * @说明 76. 最小覆盖子串
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * 注意：
 * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 * 示例 1：
 * 输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
 */
public class Solution {
    public static void main(String[] args) {
//        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
//        System.out.println(minWindow("a", "aa"));
        System.out.println(minWindow("a", "b"));
//        System.out.println(minWindow("a", "a"));
//        System.out.println(minWindow("ab", "A"));
        System.out.println(minWindow("abc", "cba"));
    }

    /**
     * 执行用时：3 ms, 在所有 Java 提交中击败了83.06%的用户
     * 内存消耗： 41.9 MB, 在所有 Java 提交中击败了67.25% 的用户
     *
     * @param s
     * @param t
     * @return
     */
    public static String minWindow(String s, String t) {
        if (t.length() > s.length()) return "";

        //转成数组,因为charAt里面有检查index是否越界步骤，会增加耗时
        char[] chars = s.toCharArray();

        //记录出现次数
        int[] intt = new int[128];
        for (int i = 0; i < 127; i++) {
            intt[i] = Integer.MIN_VALUE;
        }

        //统计t中字符出现次数
        int num = 0;
        for (int i = 0; i < t.length(); i++) {
            intt[t.charAt(i)] = intt[t.charAt(i)] == Integer.MIN_VALUE ? 1 : intt[t.charAt(i)] + 1;
            num++;
        }

        //滑动窗口
        int left = 0;
        int right = 0;

        //最小覆盖字串的头下标和长度
        int start = 0;
        int len = Integer.MAX_VALUE;
        while (right < s.length()) {
            if (right == 0) {
                if (intt[chars[right]] != Integer.MIN_VALUE) {//在intt中
                    if (intt[chars[right]] > 0) num--;
                    intt[chars[right]]--;
                    if (num == 0) return String.valueOf(chars[right]);
                }
                right++;
                continue;
            }
            while (num > 0 && right < s.length()) {
                if (intt[chars[right]] != Integer.MIN_VALUE) {//在intt中
                    if (intt[chars[right]] > 0) num--;
                    intt[chars[right]]--;
                }
                right++;
            }

            while (num == 0 && left < s.length()) {
                //滑动窗口中，属于t的
                if (intt[chars[left]] != Integer.MIN_VALUE && intt[chars[left]] < 0) {
                    intt[chars[left]]++;
                } else if (intt[chars[left]] == 0) {
                    if (len > right - left) {//挑战最小窗口
                        len = right - left;
                        start = left;
                    }
                    intt[chars[left]]++;
                    num++;
                }
                left++;
            }
        }
        if (len == Integer.MAX_VALUE) return "";
        return s.substring(start, start + len);
    }
}
